/*
 总体设计思路在report里面已经说明，这里具体解释每一个函数所起的作用
/**
*/
 
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include"dsexceptions.h"
#include<algorithm>
#define MAX 100
using namespace std;
 

map<char,int> p;
 
/**这里声明并定义一个节点，这个节点的作用是在入栈和入列时能够知道
*其元素类型，因为这里有两个类型，操作符和操作数
*/
struct Node{
	double num;//操作数
	char op;//操作符
	bool flag;//true表示操作数，false表示操作符
};
typedef struct Node node;
 
stack<node> s;//操作符栈
queue<node> q;//后缀表达式队列

/****
 *  change函数用于将中缀表达式转为后缀表达式，并且以队列的形式展现
 *其总体操作原则与报告中解释相同，在开头我进行了括号不对称的检测。如果括号不对称将进行异常抛出
**/
void change(string str){
	
	node temp;
	int flag1 =count (str.begin(),str.end(),'(');
	int flag2 =count (str.begin(),str.end(),')');
	if (flag1 != flag2){
		throw flag1;
	}
	for (int i = 0; i < str.length();){
		 if (str[i] == '('){//遇到左括号：将其入栈
			temp.flag = false;
			temp.op = str[i];
			s.push(temp);
			i++;
		}else if (str[i] == ')'){//遇到右括号：执行出栈操作，输出到后缀表达式，直到弹出的是左括号
			while (!s.empty() && s.top().op != '('){
				q.push(s.top());
				s.pop();
			}
			s.pop();//弹出左括号
			i++;
		}else if (str[i] >= '0'&&str[i] <= '9'){
			//如果是数字
			temp.flag = true;
			temp.num = str[i] - '0';
			i++;//后移一位,因为数字不一定是个位数
			while (i < str.length() && str[i] >= '0'&&str[i] <= '9'){
				temp.num = temp.num * 10 + (str[i] - '0');
				i++;
			}
			if (str[i] == '.')
			{	
				i++;
				int j=0;
				while (i < str.length() && str[i] >= '0'&&str[i] <= '9')//将数字完整提取出来，这里是遇到小数点的操作，逐个与0.1乘方相乘后再相加
					{j++;
					temp.num= temp.num + pow(0.1,j)*(str[i] - '0');
					i++;}	
			}
			q.push(temp);//操作数进入后缀表达式
		}else if (str[i]==' ' && i < str.length()){
			i++;
		}else{
			//如果是操作符
			//遇到其他运算符：弹出所有优先加大于或等于该运算符的栈顶元素，然后将该运算符入栈
			temp.flag = false;
			while (!s.empty() && p[s.top().op]>=p[str[i]]){
				q.push(s.top());
				s.pop();
			}
			temp.op = str[i];
			s.push(temp);
			i++;
		}
	}
	//将栈中剩余内容依次弹出后缀表达式
	while (!s.empty()){
		q.push(s.top());
		s.pop();
	}
}



/**
*将栈转化为带有空格的字符串，因为我所设计的下一个caculator的参数是string
**/

string swith(queue<Node> a)
{
	node temp;
	string b;
	int c;
	c= a.size();
	for (int i=0;i<c-1;i++)
	{
		temp = a.front();	
		if (temp.flag == false)
		{
			string str1(1,temp.op);
			b= b+str1+' ';
			a.pop();
		}
		else
		{	
			b= b+to_string(temp.num)+' ';
			a.pop();
		}
	}
	
	temp = a.front();
	a.pop();
	string str1(1,temp.op);
	b=b+str1;
	return b;
}
/*
*caculator函数用来计算后缀表达式
*/
double calculate(const string str)
{
	stack<double> mystack;//用来存数据
	string Empty = " ";
	string ch = "+-*/^";
	string numbers = "0123456789";
	string s = "0123456789+-*/^";
	int start, end;
	double num, secnodnum, firstnum;
	for (int i = 0; i < str.length(); )
	{
		start = str.find_first_of(s, i);//查找第一个数字或者运算符
		end = str.find_first_of(Empty, i);//查找第一空格
		if (end == -1)//处理最后一个符号后没有空格的问题
		{
			end = str.length();
		}
		string tempstr = str.substr(start, end - start);//取出这一个元素
		if ((tempstr == "+") || (tempstr == "-") || (tempstr == "*") || (tempstr == "/") || (tempstr == "^"))
		{
			secnodnum = mystack.top();//取出栈顶元素
			mystack.pop();//出栈
			firstnum = mystack.top();//取出栈顶元素
			mystack.pop();//出栈
			if (tempstr == "+")
			{
				num = firstnum + secnodnum;
				mystack.push(num);
			}
			if (tempstr == "-")
			{
				num = firstnum - secnodnum;
				mystack.push(num);
			}
			if (tempstr == "*")
			{
				num = firstnum * secnodnum;
				mystack.push(num);
			}
			if (tempstr == "/")
			{	
				if (secnodnum ==0)
				{
					throw UnderflowException();
				}
				num = firstnum / secnodnum;
				mystack.push(num);
			}
			if (tempstr == "^")
			{
				num= pow(firstnum,secnodnum);
				mystack.push(num);
			}
		}
		else
		{
			double temp = stod(tempstr);///将数字存进栈中
			mystack.push(temp);
		}
 
		i = end + 1;//控制下标的移动
	}
	return mystack.top();
}
